package com.sourcetrip.algorithm.sort.insertion;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;

/**
 * @author: ZhouBert
 * @date: 2020/12/29
 * @description: 十大排序算法之四：插入排序（的对象比较版本） --
 * 如果说，bubble selection heap 是同一类思想的排序，那么 insertion 就是另一种思想的排序。
 * --
 * 分析：
 * 将数组区分为两部分：左边排好序的部分 + 右边排好序的部分。
 * 将无序部分一个个插入到有序部分的位置。
 * --
 * 深入分析：
 * insertion sort 的时间复杂度跟【逆序对】的数量成正比！
 * 当逆序对数量很少的时候（极端情况是完全有序，O(n)复杂度），甚至比O(logn) 快速排序还快！
 * --
 * 优化：
 * 1.将 交换 改为 挪动：类似 bubble 优化到 selection ,找到 无序元素的有序位置时，一次性挪动。
 * 这样可以比交换稍微优化，因为不用频繁创建交换时的中间变量。
 */
public class InsertionCustomedSortV0<E> extends AbstractCustomedObjectSort<E> {

	/**
	 * 既然跟 bubble sort 有本质的不同，那就不能用 bubble 的模板了。
	 * insert sort 的双重 for 里面，有跟 bubble 逆向的味道。
	 * @param objectArr
	 */
	@Override
	protected void sortArr(E[] objectArr) {

		int size = objectArr.length;
		int tempIndex = 0;
		//无序部分的索引
		for (int index = 1; index < size; index++) {
			tempIndex = index;
			//有序部分
			for (int i = index - 1; i >= 0; i--) {
				if (compare(objectArr[tempIndex], objectArr[i]) < 0) {
					//无序部分比较小时进行交换（相等不需要交换，此处保证稳定）
					swap(tempIndex--, i);
				}
			}
			//此时 tempIndex 落在了正确的位置上

		}
	}
}
